// class Solution {
// public:
//     int maxProduct(vector<int>& nums) {
//         int n=nums.size();
//         int ret=0;
//         vector<int> dp(n+1,1);
//         dp[0]=1;
//         for(int i=1;i<=n;i++)
//         {
//             dp[i]=(dp[i-1]*nums[i-1],dp[i-1]);
//             ret=max(ret,dp[i]);
//         }
//         return ret;
//     }
// };


class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n=nums.size();
        vector<int> fmax(n),fmin(n);

        fmax[0]=fmin[0]=nums[0];
        int ret=nums[0];
        for(int i=1;i<n;i++)
        {
           fmax[i]=max({fmax[i-1]*nums[i],fmin[i-1]*nums[i],nums[i]});
           fmin[i]=min({fmax[i-1]*nums[i],fmin[i-1]*nums[i],nums[i]});
           ret=max({ret,fmax[i],fmin[i]});
        }
        return ret;
    }
};